﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BacktrackingCode
{
    //排序
    class Permutation
    {
        //==========================================力扣46 全排列
        //给定一个不含重复数字的数组nums，返回其所有坑你的全排列，你可以按任意顺序返回答案
        //1 <= nums.length <= 6,-10 <= nums[i] <= 10
        //排列是有序的
        List<IList<int>> result;
        List<int> path;
        public IList<IList<int>> Permute(int[] nums)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            BackTracking(nums, new bool[nums.Length]);
            return result;
        }
        void BackTracking(int[] nums, bool[] used)
        {
            if(path.Count == nums.Length)
            {// 此时说明找到了一组
                result.Add(new List<int>(path));
                return;
            }

            for(int i = 0;i<nums.Length;i++)//因为是排列，每次需要从头搜索
            {
                if (used[i] == true)
                    continue;//path已经收录的元素直接跳过

                used[i] = true;//需要used数组记录path里都放了哪些元素
                path.Add(nums[i]);
                BackTracking(nums, used);
                path.RemoveAt(path.Count - 1);
                used[i] = false;
            }
        }

        //======================================================力扣47 全排列2
        //给定一个可包含重复数字的序列 nums，按任意顺序返回所有不重复的全排列
        //1 <= nums.length <= 6,-10 <= nums[i] <= 10
        public IList<IList<int>> PermuteUnique(int[] nums)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            Array.Sort(nums);
            BackTracking_1(nums, new bool[nums.Length]);
            return result;
        }
        void BackTracking_1(int[] nums,bool[] used)
        {
            if(path.Count == nums.Length)
            {
                result.Add(new List<int>(path));
                return;
            }
            for(int i = 0;i<nums.Length;i++)
            {
                //used[i-1] == true,说明同一树枝nums[i-1]使用过
                //used[i-1] == false,说明同一树层nums[i-1]使用过
                //如果同一树层nums[i-1]使用过则跳过
                if (i > 0 && nums[i] == nums[i - 1]
                    && used[i - 1] == false)
                    continue;

                if(used[i] == false)
                {
                    used[i] = true;
                    path.Add(nums[i]);
                    BackTracking_1(nums, used);
                    path.RemoveAt(path.Count - 1);
                    used[i] = false;
                }
            }
        }

        //============================================力扣332 重新安排行程
        //给你一份航线列表tickets, 其中tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
        //所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生，所以该行程必须从JFK开始。
        //如果存在多种有效行程，请你按字典排序返回最小的行程组合
        //假定所有机票至少存在一种合理的行程，且所有的机票必须都用一次，且只能用一次
        //public IList<string> FindItinerary(IList<IList<string>> tickets)
        //{
            
        //}

    }
}
